package com.data_structure_algorithm.data_structure.array;

/**
 * @author 何章怀晓 hezhanghuaixiao
 * @version V1.0
 * @desc  稀疏数组
 */
public class SparseArr {

  public static void main(String[] args) {

    int[][] arr = new int[11][12];
    //0表示无数据
    arr[0][3] = 22;
    arr[0][6] = 15;
    arr[1][1] = 11;
    arr[1][5] = 17;
    arr[2][3] = -6;
    print("原始数组",arr);

    //将二维数组压缩
    //步骤
    //遍历二维数组 得到有效数据个数sum，根据个数创建二维数组，sum+1为行，列固定3(任何系数数组的列都是3)
    int sum = 0;
    sum = ergodic(arr, sum);
    int[][] sparseArr = new int[sum + 1][3];
    sparseArr[0][0] = arr.length;
    sparseArr[0][1] = getnum(arr);
    sparseArr[0][2] = sum;

    //将二维数组有效数据存入稀疏数组
    int count = 0;//代表有值的行列
    sparseArr = convert(arr, count, sparseArr);
    print("原始数组转为稀疏数组",sparseArr);

    //=============================================================

    //稀疏数组转为初始数组

    //读取首行数据，根据行列创建原始数组
    int row = sparseArr[0][0];
    int column = sparseArr[0][1];
    int[][] srcArr = new int[row][column];
    //遍历稀疏数组，赋值给原始二维数组
    for (int i = 1; i < sparseArr.length; i++) {
      srcArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
    }

    print("稀疏数组转为原始数组",srcArr);


  }


  private static int ergodic(int[][] arr, int sum) {
    for (int i = 0; i < arr.length; i++) {
      for (int j = 0; j < arr[i].length; j++) {

        if (arr[i][j] != 0) {
          sum++;
        }
      }
    }
    return sum;
  }

  private static int getnum(int[][] arr) {

    for (int[] item : arr
    ) {
      return item.length;

    }
    return 0;
  }

  private static int[][] convert(int[][] arr, int count, int[][] sparseArr) {
    for (int i = 0; i < arr.length; i++) {
      for (int j = 0; j < arr[i].length; j++) {
        if (arr[i][j] != 0) {
          count++;
          sparseArr[count][0] = i;
          sparseArr[count][1] = j;
          sparseArr[count][2] = arr[i][j];
        }

      }
    }
    return sparseArr;
  }

  private static void print(String name, int[][]arr) {
    System.out.println(name + "-------------------的遍历结果为--------------------");

    for (int[] item : arr
    ) {
      for (int i : item
      ) {
        System.out.print(i + " ");
      }
      System.out.println();
    }

  }



}
